package com.example.graph;

import java.util.*;

public class BFS_DFS {
    public static void main(String[] args) {

        int[][] graph = {{0, 1}, {0, 2}, {1, 2}, {1, 2}};
        int[][] g2 = {{0, 1}, {0, 2}, {0, 4}, {0, 4}, {0, 1}, {1, 3}, {1, 4}, {1, 3}, {2, 3}, {3, 4}};
        Set<Integer>[] adj = buildAdjacencyList(5, g2);


        // 邻接表实现
        Map<Integer, Set<Integer>> adj2 = buildAdjacencyList2(g2);
//        bfsTraverse(adj2, 5);
//        dfsTraverse(adj2, new boolean[5], 0);


        // 邻接矩阵实现
        int[][] adjMatrix = buildAdjacencyMatrix(5, g2);
        bfsTraverseByAdjMatrix(adjMatrix, 0);

    }

    // 邻接矩阵用Set数组表示
    public static Set<Integer>[] buildAdjacencyList(int n, int[][] graph) {
        Set<Integer>[] adj = new HashSet[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new HashSet<>();
        }
        for (int i = 0; i < graph.length; i++) {
            int from = graph[i][0];
            int to = graph[i][1];
            adj[from].add(to);
        }
        return adj;
    }

    // 邻接矩阵用map表示
    // map以顶点为key,顶点能到的其他顶点组成的Set为value
    public static Map<Integer, Set<Integer>> buildAdjacencyList2(int[][] graph) {
        Map<Integer, Set<Integer>> adj = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            int from = graph[i][0];
            int to = graph[i][1];
            adj.computeIfAbsent(from, key -> (new HashSet<>())).add(to);
        }

        return adj;
    }

    /**
     * 构建邻接矩阵
     *
     * @param n
     * @param graph
     * @return
     */
    public static int[][] buildAdjacencyMatrix(int n, int[][] graph) {
        int[][] adj = new int[n][n];

        for (int[] edge : graph) {
            int from = edge[0];
            int to = edge[1];
            adj[from][to] = 1;
        }
        return adj;
    }

    /**
     * 广度优先遍历(使用邻接表表示图)
     * <p>
     * 是从图中的任意节点（或树中的根节点）开始，探索确定当前深度所有节点的邻居节点，接着进入下一深度探索。
     * 如果所有节点均被访问，则算法中止。
     */
    public static void bfsTraverse(Map<Integer, Set<Integer>> adj, int n) {
        boolean[] visited = new boolean[n];// 用于标记节点是否被访问过
        Set<Integer> keys = adj.keySet();
        int startNode = keys.iterator().next();

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(startNode);

        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            System.out.println(tmp); // 进行遍历输出
            if (adj.get(tmp) != null) {
                Iterator<Integer> neighbors = adj.get(tmp).iterator();
                while (neighbors.hasNext()) { // 遍历邻居节点，将未访问的邻居节点入队
                    int neighbor = neighbors.next();
                    if (!visited[neighbor]) { // 判断邻居节点是否被访问过，如果访问过则要跳过该节点
                        visited[neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }

        }
    }

    /**
     * 广度优先(使用邻接矩阵表示图)
     *
     * @param adjMatrix
     * @param startNode
     */
    public static void bfsTraverseByAdjMatrix(int[][] adjMatrix, int startNode) {
        boolean[] visited = new boolean[adjMatrix.length];// 用于标记节点是否被访问过

        Queue<Integer> queue = new LinkedList<>();

        queue.offer(startNode);

        while (!queue.isEmpty()) {
            Integer tmp = queue.poll();
            System.out.println(tmp);
            for (int i = 0; i < adjMatrix[tmp].length; i++) {
                if (adjMatrix[tmp][i] != 0 && !visited[i]) {
                    visited[i] = true;
                    queue.offer(i);
                }
            }
        }

    }

    /**
     * 深度优先
     * <p>
     * 尽可能深的搜索分支，只要当前节点有邻居未被访问，就继续深入搜索；
     * 若当前节点的所在边都己被探寻过，搜索将回溯到发现当前节点那条边的起始节点。
     * 这一过程一直进行到已发现从源节点可达的所
     * 有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点
     * 并重复以上过程，直到所有节点都被访问为止。
     *
     * @param adj
     * @param visited
     * @param startNode
     */
    public static void dfsTraverse(Map<Integer, Set<Integer>> adj, boolean[] visited, int startNode) {
        System.out.println("bfs " + startNode);
        if (adj.get(startNode) != null) {
            Iterator<Integer> iterator = adj.get(startNode).iterator();
            while (iterator.hasNext()) {
                Integer tmp = iterator.next();
                if (!visited[tmp]) {
                    visited[tmp] = true;
                    dfsTraverse(adj, visited, tmp);
                }
            }
        }
    }

}
